//题目:
// 给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
// '?' 可以匹配任何单个字符。
// '*' 可以匹配任意字符序列（包括空字符序列）。
// 判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

// 示例 1：
// 输入：s = "aa", p = "a"
// 输出：false
// 解释："a" 无法匹配 "aa" 整个字符串。

// 示例 2：
// 输入：s = "aa", p = "*"
// 输出：true
// 解释：'*' 可以匹配任意字符串。

// 示例 3：
// 输入：s = "cb", p = "?a"
// 输出：false
// 解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    bool isMatch(string s, string p) 
    {
        s=" "+s,p=" "+p;
        int n1=p.size(),n2=s.size();
        //1.创建dp表————dp[i][j]表示：p的[0,i]子串能否匹配s的[0,j]子串
        vector<vector<bool>> dp(n1,vector<bool>(n2));
        //2.初始化
        dp[0][0]=true;
        for(int i=1;i<n1;i++)
            dp[i][0]=p[i]=='*'?dp[i-1][0]:false;
        //3.填表
        for(int i=1;i<n1;i++)
        {
            for(int j=1;j<n2;j++)
            {
                if(p[i]!='*' && (p[i]=='?' || p[i]==s[j]))
                    dp[i][j]=dp[i-1][j-1];
                else if(p[i]=='*')
                    dp[i][j]=dp[i][j-1] || dp[i-1][j];//重难点
            }
        }
        //4.确定返回值
        return dp[n1-1][n2-1];
    }
};